/* Поиск кратчайшего пути в графе из одной вершины */

#include <stdio.h>
#include <limits.h>

#define M INT_MAX/2

int main()
{
        int n = 6;
        int a[10][10] = {{0, 3, M, 2, M, 7},
                         {M, 0, M, M, M, M},
                         {8, M, 0, 1, 4, M},
                         {M, M, M, 0, M, 1},
                         {M, M, M, 2, 0, 5},
                         {M, M, M, M, 1, 0}};
	
	int v[10] = {0}; /* visited */
	int d[10] = {0}; /* distance */
	int w[10] = {0}; /* way */
	int i = 0;
	
	int s = 0;
	int min = 0;
	int minv = 0;
	
	for (i = 0; i < n; i++) w[i] = i;
	scanf("%d", &s);
	minv = s;
	for (i = 0; i < n; i++)
		if (i != minv) d[i] = M;	
	/* ------------------------------------ */	
	while (1)
	{
		min = M;
		for (i = 0; i < n; i++)
			if (d[i] < min && !v[i]) 
		{
			min = d[i];
			minv = i;
		}
		if (min == M) break;
		for (i = 0; i < n; i++)
			if (d[minv] + a[minv][i] < d[i]) 
			{
				d[i] = d[minv] + a[minv][i];
				w[i] = minv;
			}
		v[minv] = 1;
	}
	/* ------------------------------------ */
	for (i = 0; i < n; i++)
		if (d[i] == M) printf("M ");
		else printf("%d ", d[i]);
	printf("\n");
	for (i = 0; i < n; i++)
		if (w[i] == s) printf("D ");
		else if (d[i] == M) printf("I ");
		else printf("%d ", w[i]);
	printf("\n");
	return 0;
}
